(1) Field of the Invention
The present invention relates to an image processing device and an image processing method, and especially relates to a binarization device, a subtractive color conversion device, a binarization method, and a subtractive color conversion method of multivalued images.
(2) Description of the Prior Art
With the recent developments in computer technology, digital image processing has become commonplace. A digitized image is generally expressed by matrix data having values according to the gradation (brightness) at each sampling point. Digital image processing is attained by the numerical calculation or the like for each gradation value.
One of the problems of digital image processing is that the gradation of an image displayed by one display device can not be reproduced accurately by another display device. For instance, when a monochrome printer prints out an image displayed by a high-performance color CRT display device, the printer reproduces the image, originally displayed with 256-level gradation for each of the three primary colors of light (red, blue, and green), only with two-level gradation, or dot and blank. This problem also occurs when a CRT display device having low gradation precision displays an image displayed by a high-performance CRT display device. Therefore, image processing is necessary in order to convert the gradation values of the original image when the image is reproduced by a display device having lower gradation precision.
An error diffusion method is generally used as an image processing method performing such a conversion of gradation values. The method is expressed by the following Equations from (1) to (4), where I(x,y) represents a graduation value of the pixel at point (x,y) of the original image, and G represents a conversion function (step function) of the graduation value, and g represents the conversion result. EQU I'(x,y)=1(x,y)+E Equation (1) ##EQU1## provided ##EQU2## EQU g(x,y)=G(I'(x,y)) Equation (4)
The error diffusion method reflects the conversion error at the pixels around a pixel in a piece or pixel data to be converted by adding a diffusion error E obtained by weighting and summing conversion errors e at the surrounding pixels. In the error diffusion method, the conversion error of the whole image is smaller than that in other conventional methods, by reflecting the conversion errors around every pixel in its pixel data.
FIG. 1 is a construction of an image proccesing device that uses the error diffusion method. The image processing device includes image storage unit 2001, pixel data read unit 2002, pixel data correction unit 2003, diffusion error calculation unit 2004, pixel data conversion unit 2005, and error calculation unit 2006.
The following is a brief explanation of the operation of each unit. Pixel data read unit 2002 reads out a piece of pixel data stored in image storage unit 2001, and outputs it to pixel data correction unit 2003. Diffusion error calculation unit 2004 calculates a diffusion error E from conversion errors e output from error calculation unit 2006, and transmits it to pixel data correction unit 2003. FIG. 2 shows error diffusion coefficient aij used in diffussion error calculation unit 2004, and an example of a process which uses this error diffusion coefficient. Error diffusion coefficient aij is calculated by Equation (2), where m0=-1, m1-1, n0=-1, and n1=0. Error diffusion coefficient aij varies according to the processing direction. The error diffusion coefficients of a present pixel and the pixels located ahead of it in the processing direction are set at 0. Therefore, the diffusion error E is only calculated from the conversion errors e located behind the pixel in the processing direction as shown in FIG. 2. Pixel data correction unit 2003 adds the diffusion error E calculated by diffusion error calculation unit 2004 to the pixel data output from pixel data read unit 2002, and corrects the gradation value of the pixel data. Pixel data conversion unit 2005 converts the corrected gradation value of the pixel data to the desired binary or multivalued value by means of a function, and outputs the value to terminal T. FIG. 3A and FIG. 3B shows an example of the conversion functions used by pixel data conversion unit 2005. FIG. 3A is a table showing values that may be set by two functions f(I) and g(I) within a given range or values. FIG. 3B is a graph showing functions f(I) and g(I). These conversion functions f(I) and g(I) used by pixel data conversion unit 2005 convert gradation data expressed with 256-level gradation to gradation data expressed with seven-level gradation. Specifically, one of the two converted values of functions f(I) and g(I), closer to the original value, is used.
The following is a more detailed explanation of the above operation using the flowcharts shown in FIGS. 4, 5, and 6. Firstly, an overall explanation of the operation is given using the flowchart in FIG. 4. The initial value of each conversion error is set at 0 (Step 2301). The first scanning line is then set as the line y is equal to 0. The image is scanned with the positive direction of the y-axis as the sub scanning direction and the x-axis as the main scanning direction, with the scanning direction being positive with regard to the x-axis when y is equal to 0 or an even number and negative when y is equal to an odd number, until the top of the image is reached. During scanning, pixel data read unit 2002 reads out the pixel data, and pixel conversion unit 2005 converts the pixel data (Step 2303 to Step 2307). Although the scanning direction of the x-axis switches according to the coordinate value of the y-axis in the above example, such switching is not necessary.
Secondly, a more detailed explanation of the operation in Step 2305 and Step 2306 is given using the flowcharts shown in FIGS. 5 and 6. FIG. 5 is a flowchart showing the operation for the pixel data conversion when the image is scanned in the positive direction of the x-axis. FIG. 6 is a flowchart showing the same operation when the image is scanned in the negative direction of the x-axis. The process in these flowcharts are almost the same, so that the process will only be explained using the flowchart shown in FIG. 5. FIG. 7A to FIG. 7C show a specific example of the conversion. FIG. 7A shows the conversion direction and the position of the pixel with the coordinates (x,y). FIG. 7B shows the error diffusion coefficient aij used by diffusion error calculation unit 2004. FIG. 7C shows the conversion error e of each piece of converted pixel value and how the gradation value I of each piece of pixel data expressed with 256-level gradation is converted.
The coordinate value in the x-axis of the pixel scanned first is set at 0. The following process is performed on each scanning line in the x-axis (Step 2402 to step 2410). Pixel data correction unit 2005 substitutes the gradation value I(x,y) of the pixel positioned at coordinates (x,y) into the variable z (Step 2403). Diffusion error calculation unit 2004 calculates the diffusion error E using Equation (2) (Step 2404). For instance, the diffusion error E is calculated to be "24", using the error diffusion coefficient aij in FIG. 7B with the conversion errors c in FIG. 7C1. Pixel data correction unit 2003 uses Equation (1) to correct the pixel data by adding the diffusion error E to the variable z, into which the gradation value of the pixel data has been substituted (Step 2405). The gradation value "50" of the pixel data corresponding to the pixel positioned at coordinate (x,y) in FIG. 7C1 is corrected to "74" as shown in FIG. 7C2. Pixel data conversion unit 2005 substitutes the corrected pixel value into the two functions shown in FIG. 3 using Equation (3), and outputs the calculated value which is closer to the corrected pixel value as the converted data (Step 2406 to Step 2408). As a result, the corrected pixel value "74" in FIG. 7C2 is converted to "80" as shown in FIG. 7C3. Error calculation unit 2006 calculates the conversion error e on coordinate (x,y) using Equation (4) (Step 2409). Conversion error "-6" as shown in FIG. 7C3 is calculated from the corrected pixel value in FIG. 7C2 and the converted pixel value in FIG. 7C3.
In the conversion in FIG. 7C, since converted value "80" is larger than corrected value "74" by 6, the conversion error is "-6". The conversion error is reflected in the correction of the gradation value of the pixel data corresponding to the next pixel to decrease the converted gradation value. By repeating such a process, the overall conversion error of an image is smaller in the error diffusion method than in other methods.
The error diffusion method, however, has two problems. One of the problems is the possibility that moire patterns appear in the converted image, since the method is so sensitive to an error diffusion coefficient, which is set to reflect the conversion errors, that the converted values show a cyclical change, depending on the error diffusion coefficient. This lowers image quality.
Proposed solutions to this problem are to use a stochastic process in the conversion process or to perform the correction by the stochastic process in the conversion process. Examples are a method of changing the direction of each conversion process randomly (Japanese Laid-Open Patent Application No. 5-37781), a method of changing the combination of the coefficients randomly (Gazou Denshi-Gakkai-Shi (a periodical for the Image Electronics Academy), Vol. 20, No. 5, 1997, pp443-449), and the method of preventing the appearance of moire patterns by adding random noise to some read-out image signals (Japanese Laid-Open Patent Application No. 7-288689).
The stochastic process means a discrete stochastic process. To use the stochastic process, or to perform the correction by the stochastic process in the conversion process means to reflect a random element in the converted value. The random element is reflected by adding a random amount of noise to the converted value or the pixel data before conversion, or by selecting one converted value from a plurality of converted value options at random, or the like.
The other problem of the error diffusion method is that fine lines in the processing direction in the original image may shift or may disappear in the converted image. An example is explained with reference to FIG. 8 showing a process where a line disappears in the error diffusion method. Suppose a pixel included in a line with width 1 and having an even number y-coordinate in the original image has a gradation value "9" and the conversion error values shown in FIG. 81. The gradation values of the pixels included in the line are converted by the above-mentioned image processing device. The error diffusion coefficients shown in FIG. 7B are also used in the process. As the conversion process advances as shown in FIG. 81 to FIG. 84, the gradation values of the pixels included in the line are converted to "0". As a result, the original gradation values are converted to "0", and the line disappears. When the line comprising the pixels having gradation value "9" is included in a character, the character is illegible in the converted image.
The gradation data of the pixels included in the disappeared line remains as error data, and has an adverse effect so that bright pixels are converted to extraordinarily bright ones. Consequently, the quality of the converted image is deteriorated. Such a line-disappearing phenomenon depends on the remained conversion errors as shown in FIG. 10, even if a Floyd-type filter factor shown in FIG. 9, which is generally available, is used. In the error diffusion method, the error diffusion coefficients to prevent such phenomenon cause another problem, an even strong moire pattern.
The problem, however, is avoidable by adding a relatively large amount of noise to the pixel data having low gradation value to disturb the cyclical change of the converted gradation values.
As an example of an image processing device using the method of adding noise or performing the correction by the stochastic process for the converted value, FIG. 11 shows a construction of the image processing device according to the description of Japanese Laid-Open Patent Application No. 7 288689. The image processing device shown in FIG. 11 has data conversion correction unit 3007 including weighting coefficient generation unit 3007a, random number generation unit 3007b, multiplication unit 3007c, and addition unit 3007d, in addition to the units included in the image processing device shown in FIG. 1.
The following is a brief explanation of data conversion correction unit 3007. Weighting coefficient generation unit 3007 generates the weighting coefficient defined according to the gradation value of the pixel data read out by pixel data read unit 3002. For instance, as shown in FIG. 12A, weighting coefficient generation unit 3007 generates a weighting coefficient so that the noise is highest for pixels with middle-level gradation values that often cause moire patterns. As shown in FIG. 12B and FIG. 12C, however, it is possible for weighting coefficient generation unit 3007 to output the same weighting coefficient for all the pixels. In FIG. 12A, FIG. 12B, and FIG. 12C, weighting coefficient h(I) represents the ratio of a random number to the step width of the two step functions, or (g(I)-f(I)).
Random number generation unit 3007b generates a random number. Multiplication unit 3007c multiplies the weighting coefficient generated by weighting coefficient generation unit 3007a and the random number generated by random number generation unit 3007b. Addition unit 3007d adds the value obtained from addition unit 3007c to the pixel data corrected by pixel data correction unit 3003. By those operations, noise dependent on the gradation value of the read-out pixel data is added to the pixel data corrected by pixel data correction unit 3003. As mentioned above, by adding a suitable amount of noise, the converted values are diffused stochastically, which help prevent the appearance of moire patterns and the shifting and disappearing of fine lines in the processing direction.
The operation of the image processing device and that of the above mentioned image processing device are almost the same. The image processing device scans the original image and converts the panel data as shown in FIG. 4. FIG. 13 and FIG. 14 show the flowcharts of this image processing device and correspond to FIG. 5 and FIG. 6. The differences between the flowcharts shown in FIGS. 13 and FIG. 5, or those shown in FIG. 14 and FIG. 6 are Step 3205 or Step 3305, where noise r is generated by weighting coefficient generation unit 3007a, random number generation unit 3007b, and addition unit 3007c, and Step 3206 or Step 3306, where noise r generated by addition unit 307d is added to the corrected pixel value. In these steps, the converted values are diffused by a suitable amount. In this specification, such an error diffusion method is called the noise-adding type error diffusion method.
It is necessary for the above-mentioned noise-adding type error diffusion method to add a large amount of noise to the pixel data having lower gradation value in order to prevent fine lines in the processing direction from shifting or disappearing. The addition of such a large amount of noise for the pixel data having lower gradation, however, causes another problem, the occurrence of roughness in the converted image, leading to lower quality of the converted image. On the other hand, the use of a smaller amount of noise, in order to reduce the degree of roughness in the converted image, increases the possibility of the disappearance of tine lines and the appearance of moire patterns. Therefore, it is almost impossible for the above-mentioned noise-addding type error diffusion system to convert an image, with less roughness, no moire pattern, and no shift or disappearance of fine lines in the processing direction in the converted image.